#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElementType;
typedef struct QUEUE Queue;

struct QUEUE{
	ElementType elm;
	Queue *next;
	Queue *tail;
};


Queue * QueueInit(void){
	Queue *head=malloc(sizeof(Queue));
	head->next=NULL;
	head->tail=head;
	return head;
}
_Bool QueueEmpty(Queue *q){
	if( q->next )return false;
	return true;
}
void EnQueue(Queue *q,ElementType e){
	Queue *new=malloc(sizeof(Queue));
	new->elm=e;
	new->next=NULL;
	q->tail->next=new;
	q->tail=new;
	return;
}
ElementType DeQueue(Queue *q){
	ElementType e=q->next->elm;
	Queue *t=q->next;
	q->next=q->next->next;
	free(t);
	if( !q->next )
		q->tail=q;
	return e;
}
int max(int a,int b){
	return a>b?a:b;
}

#define N (check+1)

int main(void){
	int check,activity;
	scanf("%d %d",&check,&activity);
	int graph[N][N];
	int path[N],time[N],indegree[N];
	for(int i=0;i<N;i++){
		path[i]=-1;
		time[i]=0;
		indegree[i]=0;
		for(int j=0;j<N;j++){
			graph[i][j]=-1;
		}
	}
	int s,e,t;
	for(int i=0;i<activity;i++){
		scanf("%d %d %d",&s,&e,&t);
		graph[s][e]=t;
		indegree[e]++;
	}
	Queue *q=QueueInit();
	ElementType elm;
	for(int i=1;i<check+1;i++){
		if( 0==indegree[i] )
			EnQueue(q,i);
	}
	while( !QueueEmpty(q) ){
		elm=DeQueue(q);
		for( int i=1;i<check+1;i++ ){
			if( -1 != graph[elm][i] ){
				if( time[i] <= graph[elm][i]+time[elm] ){
					time[i]=graph[elm][i]+time[elm];
					path[i]=elm;
				}
				if( --indegree[i] == 0 )
					EnQueue(q,i);
			}
		}
	}
	int MaxTime=-1;
	for( int i=1;i<N;i++ ){
		if( indegree[i]!=0 ){
			printf("0");
			return 0;
		}
		if( time[i] > MaxTime ){
			MaxTime=time[i]
		}
	}

/*  */
	printf("\nIndex\n");
	for(int i=1;i<check+1;i++)printf("%3d",i);
	printf("\nPath\n");
	for(int i=1;i<check+1;i++)printf("%3d",path[i]);
	printf("\nTime\n");
	for(int i=1;i<check+1;i++)printf("%3d",time[i]);
	printf("\nIndegree\n");
	for(int i=1;i<check+1;i++)printf("%3d",indegree[i]);
/*  */
	return 0;
}
